/*
 * Copyright (c) 2018, apexes.net. All rights reserved.
 *
 *         http://www.apexes.net
 *
 */
package net.apexes.commons.lang;

/**
 * @author <a href="mailto:hedyn@foxmail.com">HeDYn</a>
 */
public final class Algorithms {
    private Algorithms() {}

    /**
     * <p>计算“options 选 select”的全部组合。</p><br/>
     * 例如求5中选3的组合：<br/>
     * <pre>
     * [0, 1, 2]
     * [0, 1, 3]
     * [0, 1, 4]
     * [0, 2, 3]
     * [0, 2, 4]
     * [0, 3, 4]
     * [1, 2, 3]
     * [1, 2, 4]
     * [1, 3, 4]
     * [2, 3, 4]
     * </pre>
     * m选n的组合个数公式：m!/(n!(m-n)!)
     * @param options 备选元素数量
     * @param select 选择数量
     * @param handler 组合结果消费者。为了提高性能，将共用一个数组对象传递组合结果，数组元素值为参与组合的备选元素下标。
     * @return 如果 handler 返回了非 null 的返回值，则立即中止遍历并返回该值，否则完成所有组合的遍历并返回 null
     */
    public static <T> T combination(int options, int select, IntArrayHandler<T> handler) {
        Checks.verifyNotNull(handler, "handler");
        if (options <= 0) {
            throw new IllegalArgumentException("The options must greater than 0.");
        }
        if (select <= 0) {
            throw new IllegalArgumentException("The select must greater than 0.");
        }
        if (options <= select) {
            throw new IllegalArgumentException("The options must greater than select.");
        }

        if (select == 1) {
            for (int i = 0; i < options; i++) {
                T returnValue = handler.handle(new int[] { i });
                if (returnValue != null) {
                    return returnValue;
                }
            }
            return null;
        }

        int[] result = new int[select];
        for (int i = 0; i < select; i++) {
            result[i] = i;
        }
        T returnValue = handler.handle(result);
        if (returnValue != null) {
            return returnValue;
        }

        int max = options - 1;
        while (increment(max, result)) {
            returnValue = handler.handle(result);
            if (returnValue != null) {
                return returnValue;
            }
        }
        return null;
    }

    private static boolean increment(int max, int[] array) {
        int i = array.length - 1;
        int j = i - 1;
        while (j >= 0) {
            if (array[i] + array.length - i <= max) {
                // 第i位加1
                array[i]++;
                return true;
            }
            if (array[j] + array.length - j <= max) {
                // 判断第j位加1，其后每位在前一位的基础上加1
                array[j]++;
                for (int m = j + 1; m < array.length; m++) {
                    array[m] = array[m - 1] + 1;
                }
                return true;
            }
            i--;
            j--;
        }
        return false;
    }

    /**
     * <p>计算“options 选 select”的全部组合。</p>
     * <p>算法思路是用一个数组的下标表示 1 到 options 个数，数组元素的值为1表示其下标代表的数被选中，为 0 则没选中。</p>
     * <p>首先初始化，将数组前 n 个元素置 1，表示第一个组合为前n个数。</p>
     * <p>然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。</p>
     * <p>当“1”全部移动到最右端时，就得到了最后一个组合。</p><br/>
     * 例如求5中选3的组合：<br/>
     * <pre>
     * 1   1   1   0   0   //0,1,2
     * 1   1   0   1   0   //0,1,3
     * 1   0   1   1   0   //0,2,3
     * 0   1   1   1   0   //1,2,3
     * 1   1   0   0   1   //0,1,4
     * 1   0   1   0   1   //0,2,4
     * 0   1   1   0   1   //1,2,4
     * 1   0   0   1   1   //0,3,4
     * 0   1   0   1   1   //1,3,4
     * 0   0   1   1   1   //2,3,4
     * </pre>
     * @param options 备选元素数量
     * @param select 选择数量
     * @param handler 组合结果消费者。为了提高性能，将共用一个数组对象传递组合结果，数组元素值为参与组合的备选元素下标。
     * @return 如果 consumer 返回了非 null 的返回值，则返回该值，否则返回 null
     */
    static <T> T combination2(int options, int select, IntArrayHandler<T> handler) {
        Checks.verifyNotNull(handler, "handler");
        if (options <= 0) {
            throw new IllegalArgumentException("The options must greater than 0.");
        }
        if (select <= 0) {
            throw new IllegalArgumentException("The select must greater than 0.");
        }
        if (options <= select) {
            throw new IllegalArgumentException("The options must greater than select.");
        }

        if (select == 1) {
            for (int i = 0; i < options; i++) {
                T returnValue = handler.handle(new int[] { i });
                if (returnValue != null) {
                    return returnValue;
                }
            }
            return null;
        }

        // array前select个元素都置为1
        int[] array = new int[options];
        int[] result = new int[select];
        for (int i = 0; i < select; i++) {
            array[i] = 1;
            result[i] = i;
        }
        T returnValue = handler.handle(result);
        if (returnValue != null) {
            return returnValue;
        }

        int first = 0;              // 第一个1的位置
        int swapIndexB;             // 第一个“10”中1的位置
        int swapIndexE = select;    // 第一个“10”中0的位置
        int oldSwapIndexE;
        int start;
        int i;

        while (swapIndexE < options) {
            // 将ix前的“10”改为“01”
            swapIndexB = swapIndexE - 1;
            array[swapIndexB] = 0;
            array[swapIndexE] = 1;

            oldSwapIndexE = swapIndexE;
            start = 0;
            if (first != 0) {
                // 将swopIndexB位置前的1全移到最左端
                for (i = first; i < swapIndexB; i++) {
                    if (array[i] == 0) {
                        break;
                    }
                    array[i] = 0;
                    array[start] = 1;
                    result[start] = start;
                    start++;
                }
                if (start != 0) {
                    swapIndexE = start;
                    first = 0;
                } else {
                    // 定位下一轮的swopIndexE位置
                    first = swapIndexE;
                    for (++swapIndexE; swapIndexE < options; swapIndexE++) {
                        if (array[swapIndexE] == 0) {
                            break;
                        }
                    }
                }
            } else if (swapIndexB == 0) {
                // 定位下一轮的swopIndexE位置
                first = swapIndexE;
                for (++swapIndexE; swapIndexE < options; swapIndexE++) {
                    if (array[swapIndexE] == 0) {
                        break;
                    }
                }
            } else {
                swapIndexE = swapIndexB;
            }

            for (; start < select; start++) {
                if (result[start] == swapIndexB) {
                    result[start] = oldSwapIndexE;
                    break;
                }
            }
            returnValue = handler.handle(result);
            if (returnValue != null) {
                return returnValue;
            }
        }

        return null;
    }

    /**
     * 对 options 个元素进行全排列（算法采用字典序法）。
     * @param options 参与全排列的元素数量
     * @param handler 排列结果消费者。为了提高性能，将共用一个数组对象传递排列结果，数组元素值为参与排列的备选元素下标。
     * @return 如果 handler 返回了非 null 的返回值，则立即中止遍历并返回该值，否则完成所有全排列的遍历并返回 null
     */
    public static <T> T permutation(int options, IntArrayHandler<T> handler) {
        Checks.verifyNotNull(handler, "handler");
        if (options <= 0) {
            throw new IllegalArgumentException("The options must greater than 0.");
        }
        int[] array = new int[options];
        for (int i = 0; i < options; i++) {
            array[i] = i;
        }
        T returnValue = handler.handle(array);
        if (returnValue != null) {
            return returnValue;
        }

        int end = array.length - 1;
        int index1;
        int index2;
        int temp;
        int i;
        int j;

        while (true) {
            index1 = end;
            index2 = end;
            while (index1 > 0 && array[index1] <= array[index1 - 1]) {
                index1--;
            }
            if (index1 != 0) {
                i = index1 - 1;
                while (index2 > 0 && array[index2] <= array[i]) {
                    index2--;
                }

                temp = array[i];
                array[i] = array[index2];
                array[index2] = temp;

                for (i = index1, j = end; i < j; i++, j--) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }

                returnValue = handler.handle(array);
                if (returnValue != null) {
                    return returnValue;
                }
            } else {
                break;
            }
        }

        return null;
    }

    /**
     * 接收int型数组结果的消费者
     *
     * @author <a href="mailto:hedyn@foxmail.com">HeDYn</a>
     */
    public interface IntArrayHandler<T> {
        /**
         * 接收运算结果
         * @param indexs 下标结果
         * @return 返回非NULL值将中止运行
         */
        T handle(int[] indexs);
    }

}
